//
//  Problem897.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/6/3.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 897. 递增顺序搜索树
 给你一棵二叉搜索树，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

 示例 1：
     输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
     输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
 示例 2：
     输入：root = [5,1,7]
     输出：[1,null,5,null,7]

 提示：
     树中节点数的取值范围是 [1, 100]
     0 <= Node.val <= 1000
 */
@objcMembers class Problem897: NSObject {
    func solution() {
        let root = TreeNode(5)
        root.left = TreeNode(3)
        root.left?.left = TreeNode(2)
        root.left?.left?.left = TreeNode(1)
        root.left?.right = TreeNode(4)
        
        root.right = TreeNode(6)
        root.right?.right = TreeNode(8)
        root.right?.right?.left = TreeNode(7)
        root.right?.right?.right = TreeNode(9)
        
        let node = increasingBST(root)
        print(printNodeTree(node))
    }
    
    /*
     DFS 深度优先搜索
     1: 让根节点root的left变成: 左侧中序树 = leftTree，
     2: 找到leftTree的最后一位leftNodeRight，让它的右节点leftNodeRight.right = root
     3: 让根节点root的right变成: 右侧中序树 = rigthTree，root.right = rigthTree
     */
    func increasingBST(_ root: TreeNode?) -> TreeNode? {
        if root == nil {
            return root
        } else if root?.left == nil {
            root?.right = increasingBST(root?.right)
            return root
        }
        let node = increasingBST(root?.left)
        var nodeRight = node
        while nodeRight?.right != nil {
            nodeRight = nodeRight?.right
        }
        nodeRight?.right = root
        root?.left = nil
        root?.right = increasingBST(root?.right)
        return node
    }
}
